#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void numDistinctHelper(const string &S, const string &T, int &ans)
{
    if (T.size() == 0) {ans++; return;}
    if (S.size() == 0) return;

    for (int i = 0; i < S.size(); i++) {
	if (S[i] == T[0]) 
	    numDistinctHelper(S.substr(i+1), T.substr(1), ans);
    }

}

int numDistinct(string S, string T) 
{
    int ans = 0;
    numDistinctHelper(S, T, ans);
    return ans;
}

//dynamic programming
//pass all the test on 1337
int numDistinct2(string S, string T) 
{
    vector<vector<int> > dp(S.size()+1, vector<int>(T.size()+1, 0));
    dp[0][0] = 1;
    for (int i = 1; i<= S.size(); i++) {
	    dp[i][0] = 1;
    }


    for (int i = 1; i <= S.size(); i++) {
	for (int j = 1; j <= T.size(); j++) {
	    if (S[i-1] == T[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
	    else dp[i][j] = dp[i-1][j];    
	}
    }

    for (int i = 1; i <= S.size(); i++) {
	for (int j = 1; j <= T.size(); j++) {
	    cout << dp[i][j] << " ";
	}
	cout << endl;
    }
    return dp[S.size()][T.size()]; 
}


int main(int argc, char **argv)
{
    string S = "rabbbit";
    string T = "rabbit";
    cout << numDistinct2(S, T) << endl;
}
